<!DOCTYPE HTML>

<!-- 
Strata by HTML5 UP
html5up.net | @n33co
Free for personal and commercial use under the CCA 3.0 license (html5up.net/license)
-->
<html>
	<head>
		<title>Posts &middot; Blog for Ysc</title>
		<meta charset="utf-8" />
		<meta name="viewport" content="width=device-width, initial-scale=1" />
		<meta name="author" content="Your name">
		<meta name="description" content="Describe your website">
		<meta http-equiv="content-language" content="en-us" />

		
		<meta name="og:site_name" content="Blog for Ysc">
		<meta name="og:title" content="Posts">
		<meta name="og:url" content="https://yeeeesc.gitee.io/post/">
		
		<meta name="og:image" content="https://yeeeesc.gitee.io/images/avatar.jpg">
		
		

		<meta name="generator" content="Hugo 0.69.2" />

		<!--[if lte IE 8]><script src='https://yeeeesc.gitee.io/js/ie/html5shiv.js'></script><![endif]-->
		<link rel="stylesheet" type="text/css" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css">
		<link rel="stylesheet" href="https://yeeeesc.gitee.io/css/main.css" />
		<!--[if lte IE 8]><link rel="stylesheet" href="https://yeeeesc.gitee.io//css/ie8.css"><![endif]-->

		
		<link href="https://yeeeesc.gitee.io/post/index.xml" rel="alternate" type="application/rss+xml" title="Blog for Ysc" />
		<link href="https://yeeeesc.gitee.io/post/index.xml" rel="feed" type="application/rss+xml" title="Blog for Ysc" />
		
		
	</head>

	<body id="top">
		<!-- Header -->
<header id="header">
	
	<a href="https://yeeeesc.gitee.io/" class="image avatar"><img src="https://yeeeesc.gitee.io/images/avatar.jpg" alt="" /></a>
	
	
		<h1><strong>I&rsquo;m Strata</strong>, a super simple<!-- raw HTML omitted --> responsive site template freebie<!-- raw HTML omitted --> crafted by <a href="//html5up.net">HTML5 UP</a>.</h1>
	

	
		<nav id="sidebar">
			<ul>
			
				<li><a href="https://yeeeesc.gitee.io/">Home</a></li>
			
				<li><a href="https://yeeeesc.gitee.io/post/">Blog</a></li>
			
			</ul>
		</nav>
	
</header>


		<!-- Main -->
		<div id="main">
			
    

    
    
        <span>
    <h1>
        <a href="https://yeeeesc.gitee.io/post/binary-tree-traversal/">Binary tree traversal</a>
    </h1>

    <i class="fa fa-calendar"></i>&nbsp;&nbsp;
<time datetime="2020-10-27 13:39:46 &#43;0200 &#43;0200">2020-10-27</time>&nbsp;&nbsp;




    
    
        <i class="fa fa-folder"></i>&nbsp;&nbsp;
        
        <a class="article-category-link" href="https://yeeeesc.gitee.io/categories/algorithm">Algorithm</a>
        
        
    



   
   


</span>

<p>Part 1. Preorder class Solution { public: vector&lt;int&gt; preorderTraversal(TreeNode* root) { vector&lt;int&gt; ans; if (!root) return ans; stack&lt;TreeNode*&gt; s; s.push(root); while (!s.empty()){ TreeNode* Top = s.top(); s.pop(); ans.push_back(Top-&gt;val); if (Top-&gt;right) s.push(Top-&gt;right); if (Top-&gt;left) s.push(Top-&gt;left); } return ans; } }; Part 2. Inorder class Solution { public: vector&lt;int&gt; inorderTraversal(TreeNode* root) { vector&lt;int&gt; ans; if (!root) return ans; stack&lt;TreeNode*&gt; stk; while (!stk.empty() || root){ while (root){ stk.push(root); root = root-&gt;left; } root = stk.</p>
<hr>

    
        <span>
    <h1>
        <a href="https://yeeeesc.gitee.io/post/dsu/">DSU</a>
    </h1>

    <i class="fa fa-calendar"></i>&nbsp;&nbsp;
<time datetime="2020-10-19 13:39:46 &#43;0200 &#43;0200">2020-10-19</time>&nbsp;&nbsp;




    
    
        <i class="fa fa-folder"></i>&nbsp;&nbsp;
        
        <a class="article-category-link" href="https://yeeeesc.gitee.io/categories/data-structure">Data Structure</a>
        
        
    



   
   


</span>

<p>Step 1. DSU简介 一个 DSU(Disjoint Set Union)数据结构可以用来维护图形连接组件的数据，并快速查询它们。有两种操作：
① dsu.find(node x) 找到元素 x 所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合。
② dsu.union(node x, node y) 把元素 x 和元素 y 所在的集合合并，要求 x和 y 所在的集合不相交，如果相交则不合并。
为了实现这一点，我们跟踪父结点，它会记录同一连接节点中较小结点的所在的集合。如果结点是它自己的父结点，我们将其称为连接结点的领导者。
Step 2. 代码实现 我们使用两种技术来提高运行时的复杂性：路径压缩和按秩合并。
路径压缩涉及将 find 函数中的 x=parent[x] 更改为 parent[x]=find(parent[x])。 按秩合并涉及到将发现的工作量平均分配给领导者。每当 dsu.union(x, y) 时，我们都有两个领导者 xr，yr，并且我们要选择是要 parent[x]=yr 还是 parent[y]=xr。我们选择有更多子节点的领导者作为领导者。
具体地说，rank 的含义是 x 的跟随者少于 2 ^ rank[x]，这个策略可以作为 dsu.find 中的递归循环可中的界限。
class DSU { public: DSU(int size) { parent = new int[size]; for (int i = 0; i &lt; size; i++) parent[i] = i; rank = new int[size]; } int find(int x) { if (parent[x] !</p>
<hr>

    
        <span>
    <h1>
        <a href="https://yeeeesc.gitee.io/post/blog-template/">Floyd</a>
    </h1>

    <i class="fa fa-calendar"></i>&nbsp;&nbsp;
<time datetime="2020-10-19 13:39:46 &#43;0200 &#43;0200">2020-10-19</time>&nbsp;&nbsp;




    
    
        <i class="fa fa-folder"></i>&nbsp;&nbsp;
        
        <a class="article-category-link" href="https://yeeeesc.gitee.io/categories/algorithm">Algorithm</a>
        
        
    



   
   


</span>

<p>Step 1. word
Step 2. code Step 3. answer？
   Step 4. word</p>
<hr>

    
        <span>
    <h1>
        <a href="https://yeeeesc.gitee.io/post/floyd/">Floyd</a>
    </h1>

    <i class="fa fa-calendar"></i>&nbsp;&nbsp;
<time datetime="2020-10-19 13:39:46 &#43;0200 &#43;0200">2020-10-19</time>&nbsp;&nbsp;




    
    
        <i class="fa fa-folder"></i>&nbsp;&nbsp;
        
        <a class="article-category-link" href="https://yeeeesc.gitee.io/categories/algorithm">Algorithm</a>
        
        
    



   
   


</span>

<p>Step 1. 思路 假设图上的任意两个点，已知两点间的路径权值，如果在图中能够找到一个点, 使其成为两点间的桥点，并且构成的新路径值小于旧路径值。则新路比旧路更短，由此可以得到一个递推公式：
d[u][v]=min(d[u][v],d[u][k]+d[k][v])
Step 2. 代码实现 for (int k = 1; k &lt;= n; k++) for (int i = 1; i &lt;= n; i++) for (int j = 1; j &lt;= n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); Step 3. 潜在疑惑 由于d[i][k]，d[k][j]在不断更新，而不是恒定的最小值，所以如何保证d[i][j]在最后一次更新的时候，d[i][k]，d[k][j]一定是最小的 ?
 令任意两点i和j之间的路径上可选择经过的结点集合中，桥点编号最大的是k，当k=x的时候，d[i][j]得到最小值。 设i-x中的桥点编号最大的为x1 ,x-j中编号最大的为x2 易得x&gt;x1 ,x&gt;x2① 假设此时命题成立，则x=$x_1$时，d[i][x]最小，x=x2 时，d[x][j]最小 由此可以得到x=k的时候d[i][x]+d[x][j]已经是最小了,那么e[i][j]=min(e[i][j]，e[i][x]+e[x][j])必然可以得到最小值  Step 4. 原先的错误想法以及更正 假设x1 &gt; k ，当 x = k，由于d[i][k] 还未取得最小值, 故d[i][k] + d[k][j]并没有取到最大值。所以命题①错误？事实上因为i-j的桥点编号最大的必然是k，此时令 k = x1 , 则 d[i][k]的桥点编号皆小于k, 故当 x = k 时，d[i][k]和d[k][j]  ，因此f[i][j]可以取到最大值。 当 x2 &gt; k 时同理。</p>
<hr>

    

    


		</div>

		<!-- Footer -->
<footer id="footer">
	<ul class="icons">
		
		
		
		<li><a href="//twitter.com/spf13" target="_blank" class="icon fa-twitter"><span class="label">Twitter</span></a></li>
		
		
		<li><a href="//github.com/spf13" target="_blank" class="icon fa-github"><span class="label">GitHub</span></a></li>
		
		
		<li><a href="//gitlab.com/spf13" target="_blank" class="icon fa-gitlab"><span class="label">GitLab</span></a></li>
		
		
		
		
		
		<li><a href="https://yeeeesc.gitee.io/#contact-form" class="icon fa-envelope-o"><span class="label">Email</span></a></li>
		
		
		<li><a href="https://yeeeesc.gitee.io/post/index.xml" class="icon fa-rss" type="application/rss+xml"><span class="label">RSS</span></a></li>
		
	</ul>

	<ul class="copyright">
		
		<li>© John Doe</li>
		
		<li>Design: <a href="//html5up.net">HTML5 UP</a></li>
		
		<li>Demo Images: <a href="//unsplash.com/">Unsplash</a></li>
		
	</ul>
</footer>

<!-- Scripts -->
<script src="https://yeeeesc.gitee.io/js/jquery.min.js"></script>
<script src="https://yeeeesc.gitee.io/js/jquery.poptrox.min.js"></script>
<script src="https://yeeeesc.gitee.io/js/skel.min.js"></script>
<script src="https://yeeeesc.gitee.io/js/util.js"></script>

<script src="https://yeeeesc.gitee.io/js/main.js"></script>





	</body>
</html>
